package com.lee.algorithm.linkedlist;

import com.lee.algorithm.linkedlist.struct.OneWayRandNode;

import java.util.HashMap;

/***
 * @description: 复制含有随机指针节点的链表
 *      难点：找新元素的 rand
 * @author : 青石路
 * @date: 2021/11/29 22:38
 */
public class CopyOneWayRandList {

    public static void main(String[] args) {
        OneWayRandNode<Integer> head = new OneWayRandNode<Integer>(3);
        OneWayRandNode<Integer> n1 = new OneWayRandNode<Integer>(6);
        OneWayRandNode<Integer> n2 = new OneWayRandNode<Integer>(7);
        OneWayRandNode<Integer> n3 = new OneWayRandNode<Integer>(8);
        head.next = n1;
        n1.next = n2;
        n2.next = n3;
        head.rand = n2;
        n1.rand = n2;

        // OneWayRandNode<Integer> copy = copy(head);
        OneWayRandNode<Integer> copy = copyPlus(head);
        System.out.println();
    }

    /**
     * 引入哈希表
     *      HashMap<Node, Node>，key是原链表的元素，value是 key 的克隆元素
     * @param head
     * @return
     */
    public static OneWayRandNode<Integer> copy(OneWayRandNode<Integer> head) {
        if (head == null) {
            return null;
        }
        HashMap<OneWayRandNode<Integer>, OneWayRandNode<Integer>> map = new HashMap<>();
        OneWayRandNode<Integer> cur = head;
        while(cur != null) {
            map.put(cur, new OneWayRandNode<>(cur.value));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            OneWayRandNode<Integer> clone = map.get(cur);
            if (cur.next != null) {
                clone.next = map.get(cur.next);
            }
            if (cur.rand != null) {
                clone.rand = map.get(cur.rand);
            }
            cur = cur.next;
        }
        return map.get(head);
    }

    /**
     * 原链表的拷贝元素接到其来源元素的next，例如
     *      1 -> 2 -> 3 -> null
     *      1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null
     *      那么
     *      1'.next = 1.next.next.next
     *      1'.rand = 1.rand != null ? 1.rand.next : null
     *      最后拆分出新链表与旧链表
     *
     * 原理：
     *      克隆节点的位置的特殊性，省去了哈希表
     * @param head
     * @return
     */
    public static OneWayRandNode<Integer> copyPlus(OneWayRandNode<Integer> head) {
        if (head == null) {
            return null;
        }

        // 原链表的拷贝元素接到其来源元素的next
        OneWayRandNode<Integer> cur = head;
        OneWayRandNode<Integer> next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = new OneWayRandNode<Integer>(cur.value);
            cur.next.next = next;
            cur = next;
        }

        // 寻找 clone 节点的 rand
        cur = head;
        OneWayRandNode<Integer> curCopy = null;
        // 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null
        while (cur != null) {
            next = cur.next.next;
            curCopy = cur.next;
            curCopy.rand = cur.rand != null ? cur.rand.next : null;
            cur = next;
        }

        // 原链表与克隆链表拆分
        OneWayRandNode<Integer> cloneHead = head.next;
        cur = head;
        while (cur != null) {
            next = cur.next.next;
            curCopy = cur.next;
            cur.next = next;
            curCopy.next = next != null ? next.next : null;
            cur = next;
        }
        return cloneHead;
    }
}
